Skeleton growing and pruning with bending potential ratio.

Convex shape decomposition.

Two%2DStep Coding for High Definition Video Compression.



Boosting Chamfer Matching by Learning Chamfer Distance Normalization.
Abstract. We propose a novel technique that significantly improves the performance of oriented chamfer matching on images with cluttered background. Different to other matching methods, which only measures how well a template fits to an edge map, we evaluate the score of the template in comparison to auxiliary contours, which we call normalizers. We utilize AdaBoost to learn a Normalized Oriented Chamfer Distance (NOCD). Our experimental results demonstrate that it boosts the detection rate of the oriented chamfer distance. The simplicity and ease of training of NOCD on a small number of training samples promise that it can replace chamfer distance and oriented chamfer distance in any template matching application. 1
Weakly Supervised Shape Based Object Detection with Particle Filter.
Abstract. We describe an efficient approach to construct shape models composed of contour parts with partially-supervised learning. The proposed approach can easily transfer parts structure to different object classes as long as they have similar shape. The spatial layout between parts is described by a non-parametric density, which is more flexible and easier to learn than commonly used Gaussian or other parametric distributions. We express object detection as state estimation inference executed using a novel Particle Filters (PF) framework with static observations, which is quite different from previous PF methods. Although the underlying graph structure of our model is given by a fully connected graph, the proposed PF algorithm efficiently linearizes it by exploring the conditional dependencies of the nodes representing contour parts. Experimental results demonstrate that the proposed approach can not only yield very good detection results but also accurately locates contours of target objects in cluttered images. 1
Contour based object detection using part bundles.

Learning Context%2DSensitive Shape Similarity by Graph Transduction.

Skeletonization with Particle Filters.
Abstract. We present a novel method to obtain high quality skeletons of binary shapes. The obtained skeletons are connected and one pixel thick. They do not require any pruning or any other post-processing. The computation is composed of two major parts. First, a small set of salient contour points is computed. We use Discrete Curve Evolution, but any other robust method could be used. Second, particle filters are used to obtain the skeleton. The main idea is that the particles walk along the skeletal paths between pairs of the salient points. We provide experimental results that clearly demonstrate that the proposed method significantly outperforms other well-known methods for skeleton computation.
Shape band A deformable object detection approach.
In this paper, we focus on the problem of detecting/matching a query object in a given image. We propose a new algorithm, shape band, which models an object within a bandwidth of its sketch/contour. The features associated with each point on the sketch are the gradients within the bandwidth. In the detection stage, the algorithm simply scans an input image at various locations and scales for good candidates. We then perform fine scale shape matching to locate the precise object boundaries, also by taking advantage of the information from the shape band. The overall algorithm is very easy to implement, and our experimental results show that it can outperform stat-of-the-art contour based object detection algorithms. 1.
Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval.
The matching and retrieval of 2D shapes is an important challenge in computer vision. A large number of shape similarity approaches have been developed, with the main focus being the comparison or matching of pairs of shapes. In these approaches, other shapes do not influence the similarity measure of a given pair of shapes. In the proposed approach, other shapes do influence the similarity measure of each pair of shapes, and we show that this influence is beneficial even in the unsupervised setting (without any prior knowledge of shape classes). The influence of other shapes is propagated as a diffusion process on a graph formed by a given set of shapes. However, the classical diffusion process does not perform well in shape space for two reasons: it is unstable in the presence of noise and the underlying local geometry is sparse. We introduce a locally constrained diffusion process which is more stable even if noise is present, and we densify the shape space by adding synthetic points we call ’ghost points’. We present experimental results that demonstrate very significant improvements over state-of-the-art shape matching algorithms. On the MPEG-7 data set, we obtained a bull’s-eye retrieval score of 93.32%, which is the highest score ever reported in the literature. 1.
Improving SVM Classification on Imbalanced Data Sets in Distance Spaces.
Abstract—Imbalanced data sets present a particular challenge to the data mining community. Often, it is the rare event that is of interest and the cost of misclassifying the rare event is higher than misclassifying the usual event. When the data is highly skewed toward the usual, it can be very difficult for a learning system to accurately detect the rare event. There have been many approaches in recent years for handling imbalanced data sets, from under-sampling the majority class to adding synthetic points to the minority class in feature space. Distances between time series are known to be non-Euclidean and nonmetric, since comparing time series requires warping in time. This fact makes it impossible to apply standard methods like SMOTE to insert synthetic data points in feature spaces. We present an innovative approach that augments the minority class by adding synthetic points in distance spaces. Wethenuse Support Vector Machines for classification. Our experimental results on standard time series show that our synthetic points significantly improve the classification rate of the rare events, and in many cases also improves the overall accuracy of SVM. Keywords-imbalanced data sets; support vector machines; time series; I.
Outlier Detection with Globally Optimal Exemplar%2DBased GMM.
Outlier detection has recently become an important problem in many data mining applications. In this paper, a novel unsupervised algorithm for outlier detection is proposed. First we apply a provably globally optimal Expectation Maximization (EM) algorithm to fit a Gaussian Mixture Model (GMM) to a given data set. In our approach, a Gaussian is centered at each data point, and hence, the estimated mixture proportions can be interpreted as probabilities of being a cluster center for all data points. The outlier factor at each data point is then defined as a weighted sum of the mixture proportions with weights representing the similarities to other data points. The proposed outlier factor is thus based on global properties of the data set. This is in contrast to most existing approaches to outlier detection, which are strictly local. Our experiments performed on several simulated and real life data sets demonstrate superior performance of the proposed approach. Moreover, we also demonstrate the ability to detect unusual shapes. 1
Distance Learning Based on Convex Clustering.
Abstract. Clustering has been among the most active research topics in machine learning and pattern recognition. Though recent approaches have delivered impressive results in a number of challenging clustering tasks, most of them did not solve two problems. First, most approaches need prior knowledge about the number of clusters which is not practical in many applications. Second, non-linear and elongated clusters cannot be clustered correctly. In this paper, a general framework is proposed to solve both problems by convex clustering based on learned distance. In the proposed framework, the data is transformed from elongated structures into compact ones by a novel distance learning algorithm. Then, a convex clustering algorithm is used to cluster the transformed data. Presented experimental results demonstrate successful solutions to both problems. In particular, the proposed approach is very suitable for superpixel generation, which are a common base for recent high level image segmentation algorithms. 1
Outlier Detection with Globally Optimal Exemplar%2DBased GMM.
Outlier detection has recently become an important problem in many data mining applications. In this paper, a novel unsupervised algorithm for outlier detection is proposed. First we apply a provably globally optimal Expectation Maximization (EM) algorithm to fit a Gaussian Mixture Model (GMM) to a given data set. In our approach, a Gaussian is centered at each data point, and hence, the estimated mixture proportions can be interpreted as probabilities of being a cluster center for all data points. The outlier factor at each data point is then defined as a weighted sum of the mixture proportions with weights representing the similarities to other data points. The proposed outlier factor is thus based on global properties of the data set. This is in contrast to most existing approaches to outlier detection, which are strictly local. Our experiments performed on several simulated and real life data sets demonstrate superior performance of the proposed approach. Moreover, we also demonstrate the ability to detect unusual shapes. 1


A Video Coding Scheme Based on Joint Spatiotemporal and Adaptive Prediction.
Abstract—We propose a video coding scheme that departs from traditional Motion Estimation / DCT frameworks and instead uses Karhunen-Loeve Transform (KLT)  / Joint Spatiotemporal Prediction framework. In particular, a novel approach that performs joint spatial and temporal prediction simultaneously is introduced. It bypasses the complex H.26x inter-frame techniques and it is less computationally intensive. Because of the advantage of the effective joint prediction and the image-dependent color space transformation (KLT), the proposed approach is demonstrated experimentally to consistently lead to improved video quality, and in many cases to better compression rates and improved computational speed.
Contour Grouping Based on Contour%2DSkeleton Duality.
Abstract In this paper we present a method for grouping relevant object contours in edge maps by taking advantage of contour-skeleton duality. Regularizing contours and skeletons simultaneously allows us to combine both low level perceptual constraints as well as higher level model constraints in a very effective way. The models are represented using paths in symmetry sets. Skeletons are treated as trajectories of an imaginary virtual robot in a discrete space of “symmetric points ” obtained from pairs of edge segments. Boundaries are then defined as the maps obtained by grouping the associated pairs of edge segments along the trajectories. Casting the grouping problem in this manner makes it similar to the problem of Simultaneous Localization and Mapping (SLAM). Hence we adapt the state-of-theart probabilistic framework namely Rao-Blackwellized particle filtering that has been successfully applied to SLAM. We use the framework to maximize the joint posterior over skeletons and contours.
Improving Shape Retrieval by Learning Graph Transduction.
Abstract. Shape retrieval/matching is a very important topic in computer vision. The recent progress in this domain has been mostly driven by designing smart features for providing better similarity measure between pairs of shapes. In this paper, we provide a new perspective to this problem by considering the existing shapes as a group, and study their similarity measures to the query shape in a graph structure. Our method is general and can be built on top of any existing shape matching algorithms. It learns a better metric through graph transduction by propagating the model through existing shapes, in a way similar to computing geodesics in shape manifold. However, the proposed method does not require learning the shape manifold explicitly and it does not require knowing any class labels of existing shapes. The presented experimental results demonstrate that the proposed approach yields significant improvements over the state-of-art shape matching algorithms. We obtained a retrieval rate of 91 % on the MPEG-7 data set, which is the highest ever reported in the literature. 1
Merging maps of multiple robots.
Merging local maps, acquired by multiple robots, into a global map, (also known as map merging) is one of the important issues faced by virtually all cooperative exploration techniques. We present a novel and simple solution to the problem of map merging by reducing it to the problem of SLAM of a single ”virtual” robot. The individual local maps and their shape information constitute the sensor information for the virtual robot. This approach allows us to adapt the framework of Rao-Blackwellized particle filtering used in SLAM of a single robot for the problem of map merging. 1
Contour Extraction Using Particle Filters.
Abstract. This paper describes a novel approach to extract object region from an image by tracking the enclosing contour. We assume that the image is not complex, and it can be roughly partitioned into two parts with an intensity threshold. A lot of images (for example medical images) are in accord with this assumption. Global constraint (threshold) and local constraint (gradient) are integrated in a particle filter framework. We utilize the filter to track the optimal contour path pixel by pixel. The processing time depends only on the contour length and the number of particles used. Thus the proposed method is significantly faster than the very popular and time consuming method: Active Contour Models (“Snakes”). Both Snakes and our method are targeted for similar applications. Experimental results illustrate the validity and advantages of our method. 1
Symmetry of Shapes Via Self%2Dsimilarity.
Abstract. We describe a simple and novel approach to identify main similarity axes by maximizing self-similarity of object contour parts divided by the axes. For a symmetric or approximately symmetric shape, the main self-similarity axis coincides with the main axis of symmetry. However, the concept of the main self-similarity axis is more general, and significantly easier to compute. By identifying critical points on the contour self-similarity computation can be expressed as a discrete problem of finding two subsets of the critical points such that the two contour parts determined by the subsets are maximally similar. In other words, for each shape, we compute its division into two parts so that the parts are maximally similar. Our experimental results yield correctly placed maximal symmetry axes for articulated and highly distorted shapes. 1
Multiscale Random Fields with Application to Contour Grouping.
We introduce a new interpretation of multiscale random fields (MSRFs) that admits efficient optimization in the framework of regular (single level) random fields (RFs). It is based on a new operator, called append, that combines sets of random variables (RVs) to single RVs. We assume that a MSRF can be decomposed into disjoint trees that link RVs at different pyramid levels. The append operator is then applied to map RVs in each tree structure to a single RV. We demonstrate the usefulness of the proposed approach on a challenging task involving grouping contours of target shapes in images. It provides a natural representation of multiscale contour models, which is needed in order to cope with unstable contour decompositions. The append operator allows us to find optimal image segment labels using the classical framework of relaxation labeling. Alternative methods like Markov Chain Monte Carlo (MCMC) could also be used. 1
Computing Stable Skeletons with Particle Filters.
Abstract. We present a novel method to obtain high quality skeletons of binary shapes. The obtained skeletons are connected and one pixel thick. They do not require any pruning or any other post-processing. The computation is composed of two major parts. First, a small set of salient contour points is computed. We use Discrete Curve Evolution, but any other robust method could be used. Second, particle filters are used to obtain the skeleton. The main idea is that the particles walk along the skeletal paths between pairs of the salient points. We provide experimental results that clearly demonstrate that the proposed method significantly outperforms other well-known methods for skeleton computation.
Towards a Generalization of Self%2Dlocalization.
Summary. Self-localization is an important task for humans and autonomous robots as it is the basis for orientation and navigation in a spatial environment and for performing mapping tasks. In robotics, self-localization on the basis of monomodal perceptual information has been investigated intensively. The present chapter looks at self-localization in a more general setting where the reference information may be provided by different types of sensors or by descriptions of locations under a variety of conditions. We introduce some of these conditions and discuss general approaches to identifying locations in perceived environments. Taking into account cognitive considerations, we propose an approach to identify locations on a high, abstract level of representation. The approach combines qualitative and quantitative information to recognize locations described as configurations of shape features. We evaluate this approach in comparison to other approaches in a selflocalization task and a generalized localization task based on a schematic map. 1
Path Similarity Skeleton Graph Matching.
This paper proposes a novel graph matching algorithm and applies it to shape recognition based on object silhouettes. The main idea is to match skeleton graphs by comparing the geodesic paths between skeleton endpoints. In contrast to typical tree or graph matching methods, we do not consider the topological graph structure. Our approach is motivated by the fact that visually similar skeleton graphs may have completely different topological structures. The proposed comparison of geodesic paths between endpoints of skeleton graphs yields correct matching results in such cases. The skeletons are pruned by contour partitioning with Discrete Curve Evolution, which implies that the endpoints of skeleton branches correspond to visual parts of the objects. The experimental results demonstrate that our method is able to produce correct results in the presence of articulations, stretching, and contour deformations.
Skeleton%2DBased Shape Classification Using Path Similarity.

A Unified Curvature Definition for Regular
Abstract In this paper, we propose a new definition of curvature, called visual curvature. It is based on statistics of the extreme points of the height functions computed over all directions. By gradually ignoring relatively small heights, a multi-scale curvature is obtained. The theoretical properties and the experiments presented demonstrate that multi-scale visual curvature is stable, even in the presence of significant noise. To our best knowledge, the proposed definition of visual curvature is the first ever that applies to regular curves as defined in differential geometry as well as to turn angles of polygonal curves. Moreover, it yields stable curvature estimates of curves in digital images even under sever distortions. We also show a relation between multi-scale visual curvature and convexity of simple closed curves.
Topological Repairing of 3D Digital Images.

Detection and recognition of contour parts based on shape similarity.
Due to distortion, noise, segmentation errors, overlap, and occlusion of objects in digital images, it is usually impossible to extract complete object contours or to segment the whole objects. How-ever, in many cases parts of contours can be correctly reconstructed either by performing edge grouping or as parts of boundaries of segmented regions. Therefore, recognition of objects based on their contour parts seems to be a promising as well as a necessary research direction. The main contribution of this paper is a system for detection and recognition of contour parts in digital images. Both detection and recognition are based on shape similarity of contour parts. For each contour part produced by contour grouping, we use shape similarity to retrieve the most similar contour parts in a database of known contour segments. A shape-based classification of the retrieved contour parts performs then a simultaneous detection and recognition. An important step in our approach is the construction of the database of known contour segments. First complete contours of known objects are decomposed into parts using DCE (Discrete Curve Evolution). Then, their representation is constructed that is invariant to scaling, rotation, and translation.
Incremental Local Outlier Detection for Data Streams.
Abstract. Outlier detection has recently become an important problem in many industrial and financial applications. This problem is further complicated by the fact that in many cases, outliers have to be detected from data streams that arrive at an enormous pace. In this paper, an incremental LOF (Local Outlier Factor) algorithm, appropriate for detecting outliers in data streams, is proposed. The proposed incremental LOF algorithm provides equivalent detection performance as the iterated static LOF algorithm (applied after insertion of each data record), while requiring significantly less computational time. In addition, the incremental LOF algorithm also dynamically updates the profiles of data points. This is a very important property, since data profiles may change over time. The paper provides theoretical evidence that insertion of a new data point as well as deletion of an old data point influence only limited number of their closest neighbors and thus the number of updates per such insertion/deletion does not depend on the total number of points N in the data set. Our experiments performed on several simulated and real life data sets have demonstrated that the proposed incremental LOF algorithm is computationally efficient, while at the same time very successful in detecting outliers and changes of distributional behavior in various data stream applications. I.
Visual Curvature.
The Lorenz manifold is an intriguing two-dimensional surface that illustrates chaotic dynamics in the well-known Lorenz system. While it is not possible to find the Lorenz manifold as an explicit analytic solution, we have developed a method for calculating a numerical approximation that builds the surface up as successive geodesic level sets. The resulting mesh approximation can be read as crochet instructions, which means that we are able to generate a three-dimensional model of the Lorenz manifold. We mount the crocheted Lorenz manifold using a stiff rod as the z-axis, and bendable wires at the outer rim and the two solutions that are perpendicular to the z-axis. The crocheted model inspired us to consider the geometrical properties of the Lorenz manifold. Specifically, we introduce a simple method to determine and visualize local curvature of a smooth surface. The colour coding according to curvature reveals a striking pattern of regions of positive and negative curvature on the Lorenz manifold. 1
Discrete Skeleton Evolution.
Abstract. Skeleton can be viewed as a compact shape representation in that the shape can be completely reconstructed form the skeleton. We present a novel method for skeleton pruning that is based on this fundamental skeleton property. We iteratively remove skeleton end braches with smallest relevance for shape reconstruction. The relevance of branches is measured as their contribution to shape reconstruction. The proposed pruning method allows us to overcome the instability of skeleton representation: a small boundary deformation leads to large changes in skeleton topology. Consequently, we are able to obtain very stable skeleton representation of planar shapes.
Shape Classification Based on Skeleton Path Similarity.

Contour Grouping Based on Local Symmetry.%

Contour Grouping Based on Local Symmetry.%

Optimal Subsequence Bijection.
We consider the problem of elastic matching of sequences of real numbers. Since both a query and a target sequence may be noisy, i.e., contain some outlier elements, it is desirable to exclude the outlier elements from matching in order to obtain a robust matching performance. Moreover, in many applications like shape alignment or stereo correspondence it is also desirable to have a one-to-one and onto correspondence (bijection) between the remaining elements. We propose an algorithm that determines the optimal subsequence bijection (OSB) of a query and target sequence. The OSB is efficiently computed since we map the problem’s solution to a cheapest path in a DAG (directed acyclic graph). We obtained excellent results on standard benchmark time series datasets. We compared OSB to Dynamic Time Warping (DTW) with and without warping window. We do not claim that OSB is always superior to DTW. However, our results demonstrate that skipping outlier elements as done by OSB can significantly improve matching results for many real datasets. Moreover, OSB is particularly suitable for partial matching. We applied it to the object recognition problem when only parts of contours are given. We obtained sequences representing shapes by representing object contours as sequences of curvatures. 1.
Skeletonization using SSM of the Distance Transform.
This paper proposes a new approach for skeletonization based on the skeleton strength map (SSM) caculated by Euclidean distance transform of a binary image. After the distance transform and gradient are computed, isotropic diffusion is performed on the gradient vector field and the skeleton strength map is computed from the diffused vector field. A critical point set is then selected from local maxima of the SSM. The critical points are located on significant visual parts of the object. The skeleton is obtained by connecting the critical points with geodesic paths. This approach overcomes intrinsic drawbacks of distance transform based skeletons, since it yields stable and connected skeletons without losing significant visual parts. Index terms—Skeletonization, gradient vector field, isotropic diffusion, distance transform, skeleton strength map (SSM) 1.
Outlier Detection with Kernel Density Functions.

Topological Equivalence between a 3D Object and the Reconstruction of Its Digital Image.
 Digitization is not as easy as it looks. If one digitizes a 3D object even with a dense sampling grid, the reconstructed digital object may have topological distortions and, in general, there exists no upper bound for the Hausdorff distance. This explains why so far no algorithm has been known which guarantees topology preservation. However, as we will show, it is possible to repair the obtained digital image in a locally bounded way so that it is homeomorphic and close to the 3D object. The resulting digital object is always wellcomposed, which has nice implications for a lot of image analysis problems. Moreover, we will show that the surface of the original object is homeomorphic to the result of the marching cubes algorithm. This is really surprising since it means that the well-known topological problems of the marching cubes reconstruction simply do not occur for digital images of r-regular objects. Based on the trilinear interpolation, we also construct a smooth isosurface from the digital image that has the same topology as the original surface. Finally, we give a surprisingly simple topology preserving reconstruction method by using overlapping balls instead of cubical voxels. This is the first approach of digitizing 3D objects which guarantees topology preservation and gives an upper bound for the geometric distortion. Since the output can be chosen as a pure voxel presentation, a union of balls, a reconstruction by trilinear interpolation, a smooth isosurface, or the piecewise linear marching cubes surface, the results are directly applicable to a huge class of image analysis algorithms. Moreover, we show how one can efficiently estimate the volume and the surface area of 3D objects by looking at their digitizations. Measuring volume and surface area of digital objects are important problems in 3D image analysis. Good estimators should be multigrid convergent, i.e., the error goes to zero with increasing sampling density. We will show that every presented reconstruction method can be used for
Skeleton Pruning by Contour Partitioning with Discrete Curve Evolution.
Abstract—In this paper, we introduce a new skeleton pruning method based on contour partitioning. Any contour partition can be used, but the partitions obtained by Discrete Curve Evolution (DCE) yield excellent results. The theoretical properties and the experiments presented demonstrate that obtained skeletons are in accord with human visual perception and stable, even in the presence of significant noise and shape variations, and have the same topology as the original skeletons. In particular, we have proven that the proposed approach never produces spurious branches, which are common when using the known skeleton pruning methods. Moreover, the proposed pruning method does not displace the skeleton points. Consequently, all skeleton points are centers of maximal disks. Again, many existing methods displace skeleton points in order to produces pruned skeletons. Index Terms—Skeleton, skeleton pruning, contour partition, discrete curve evolution. 1
Multi robot mapping using force field simulation.

An elastic partial shape matching technique.

Properties and Performances of Shape Similarity Measures.
Abstract. This paper gives an overview of shape dissimilarity measure properties, such as metric and robustness properties, and of retrieval performance measures. Fifteen shape similarity measures are shortly described and compared. Their retrieval results on the MPEG-7 Core Experiment CE-Shape-1 test set as reported in the literature and obtained by a reimplementation are compared and discussed. 1
Skeleton Pruning by Contour Partitioning.
Abstract—In this paper, we introduce a new skeleton pruning method based on contour partitioning. Any contour partition can be used, but the partitions obtained by Discrete Curve Evolution (DCE) yield excellent results. The theoretical properties and the experiments presented demonstrate that obtained skeletons are in accord with human visual perception and stable, even in the presence of significant noise and shape variations, and have the same topology as the original skeletons. In particular, we have proven that the proposed approach never produces spurious branches, which are common when using the known skeleton pruning methods. Moreover, the proposed pruning method does not displace the skeleton points. Consequently, all skeleton points are centers of maximal disks. Again, many existing methods displace skeleton points in order to produces pruned skeletons. Index Terms—Skeleton, skeleton pruning, contour partition, discrete curve evolution. 1
Object Tracking with Dynamic Template Update and Occlusion Detec.

3D Object Digitization Majority Interpolation and Marching Cube.
In a previous paper we showed that a 3D object can be digitized without changing the topology if the object is r-regular and if the reconstruction method fulfills certain requirements. In this paper we give two important examples for such reconstruction methods. First, we introduce Majority Interpolation, an algorithm to interpolate sampling points at doubled resolution such that topological ambiguities are resolved. Second, we show how the well-known Marching Cubes algorithm has to be modified such that it is topology preserving. This is the first approach of digitizing 3D objects which guarantees topology preservation for voxel-based or polygonal surface-based reconstructions. 1
3D Object Digitization Majority Interpolation and Marching Cubes.
In a previous paper we showed that a 3D object can be digitized without changing the topology if the object is r-regular and if the reconstruction method fulfills certain requirements. In this paper we give two important examples for such reconstruction methods. First, we introduce Majority Interpolation, an algorithm to interpolate sampling points at doubled resolution such that topological ambiguities are resolved. Second, we show how the well-known Marching Cubes algorithm has to be modified such that it is topology preserving. This is the first approach of digitizing 3D objects which guarantees topology preservation for voxel-based or polygonal surface-based reconstructions. 1
Using Extended EM to Segment Planar Structures in 3D.

3D Object Digitization Topology Preserving Reconstruction.
In this paper we derive a sampling theorem, which is the first one to guarantee topology preservation during digitization of 3D objects. This new theorem is applicable to several reconstruction methods, e.g. a unionof-balls reconstruction and the trilinear interpolation. 1
Extended EM for Planar Approximation of 3D Data.

Polygonal Approximation of Laser Range Data based on Perceptual Grouping and EM.
Abstract — Our goal is polygonal approximation of laser range data points obtained by a mobile robot. The proposed approach provides a precise estimation of the number of model components (line segments) and their initial parameters independent of their initial values. We use principles of perceptual grouping to evaluate the approximation quality obtained in each Expectation Maximization (EM) step. By evaluating EM approximation quality we are able to recognize a locally optimal solution, and modify the number of model components and their parameters. Consequently, EM can converge only to a globally optimal solution independent of the initial number of model components and their initial parameters. I.
Polygonal Approximation of Point Sets.
Abstract—This paper addresses the problem of piecewise linear approximation of point sets without any constraints on the order of data points or the number of model components (line segments). We point out two problems with the maximum likelihood estimate (MLE) that present serious drawbacks in practical applications. One is that the parametric models obtained using a classical MLE framework are not guaranteed to be close to data points. It is typically impossible, in this classical framework, to detect whether a parametric model fits the data well or not. The second problem is related to accurately choosing the optimal number of model components. We first fit a nonparametric density to the data points and use it to define a neighborhood of the data. Observations inside this neighborhood are deemed informative; those outside the neighborhood are deemed uninformative for our purpose. This provides us with a means to recognize when models fail to properly fit the data. We then obtain maximum likelihood estimates by optimizing the Kullback-Leibler Divergence (KLD) between the nonparametric data density restricted to this neighborhood and a mixture of parametric models. We prove that, under the assumption of a reasonably large sample size, the inferred model components are close to their ground truth model component counterparts. This holds independently of the initial number of assumed model components or their associated parameters. Moreover, in the proposed approach, we are able to estimate the number of significant model components without any additional computation.
Using spatiotemporal blocks to reduce the uncertainty in detecting and tracking moving objects in video.

New EM derived from Kullback%2DLeibler divergence.

Using spatiotemporal blocks to reduce the uncertainty in detecting and tracking moving objects in video.

Tracking motion objects in infrared videos.

Geometric Robot Mapping.

Partial Elastic Matching of Time Series.
We consider the problem of elastic matching of time series. We propose an algorithm that determines a subsequence of a target time series that best matches a query series. In the proposed algorithm we map the problem of the best matching subsequence to the problem of a cheapest path in a DAG (directed acyclic graph). The proposed approach allows us to also compute the optimal scale and translation of time series values, which is a nontrivial problem in the case of subsequence matching.
Activity and Motion Detection Based on Measuring Texture Change.

Elastic Partial Matching of Time Series.
Abstract. We consider a problem of elastic matching of time series. We propose an algorithm that automatically determines a subsequence b ′ of a target time series b that best matches a query series a. In the proposed algorithm we map the problem of the best matching subsequence to the problem of a cheapest path in a DAG (directed acyclic graph). Our experimental results demonstrate that the proposed algorithm outperforms the commonly used Dynamic Time Warping in retrieval accuracy. 1
Instantaneous reliability assessment of motion features in surveillance videos.

Optimal partial shape similarity.
Humans are able to recognize objects in the presence of significant amounts of occlusion and changes in the view angle. In human and robot vision, these conditions are normal situations and not exceptions. In digital images one more problem occurs due to unstable outcomes of the segmentation algorithms. Thus, a normal case is that a given shape is only partially visible, and the visible part is distorted. To our knowledge there does not exist a shape representation and similarity approach that could work under these conditions. However, such an approach is necessary to solve the object recognition problem. The main contribution of this paper is the definition of an optimal partial shape similarity measure that works under these conditions. In particular, the presented novel approach to shape-based object recognition works
Shape Matching for Robot Mapping.
Abstract. We present a novel geometric model for robot mapping based on shape. Shape similarity measure and matching techniques originating from computer vision are specially redesigned for matching range scans. The fundamental geometric representation is a structural one, polygonal lines are ordered according to the cyclic order of visibility. This approach is an improvement of the underlying geometric models of today’s SLAM implementations, where shape matching allows us to disregard pose estimations. The object-centered approach allows for compact representations that are well-suited to bridge the gap from metric information needed in path planning to more abstract, i.e. topological or qualitative spatial knowledge desired in complex navigational tasks. 1
A two%2Dstream approach for adaptive rate control in multimedia applications.

Shape%2DBased Robot Mapping.
Abstract. We present a novel geometric model for robot mapping suited for robots equipped with a laser range finder. The geometric representation is based on shape. Cyclic ordered sets of polygonal lines are the underlying data structures. Specially adapted shape matching techniques originating from computer vision are applied to match range scan against the partially constructed map. Shape matching respects for a wider context than conventional scan matching approaches, allowing to disregard pose estimations. The described shape based approach is an improvement of the underlying geometric models of todays SLAM implementations. Moreover, using our object-centered approach allows for compact representations that are well-suited to bridge the gap from metric information needed in robot motion and path planning to more abstract, i.e. topological or qualitative spatial knowledge desired in complex navigational tasks or communication.
Shape Matching for Robot Mapping.
Abstract. We present a novel geometric model for robot mapping based on shape. Shape similarity measure and matching techniques originating from computer vision are specially redesigned for matching range scans. The fundamental geometric representation is a structural one, polygonal lines are ordered according to the cyclic order of visibility. This approach is an improvement of the underlying geometric models of today’s SLAM implementations, where shape matching allows us to disregard pose estimations. The object-centered approach allows for compact representations that are well-suited to bridge the gap from metric information needed in path planning to more abstract, i.e. topological or qualitative spatial knowledge desired in complex navigational tasks. 1
Detection of Changes in Surveillance Videos.
In this paper we provide theoretical and experimental results that dimension of video trajectories is a useful tool to access mid-level content of videos, like, appearance or disappearance of an object, and changes in velocity and in direction of moving objects. Moreover, the amount of changes is proportional to the size of objects involved and their speed. All this is achieved by a robust technique of dimensionality computation of video trajectories based on eigenvalues.
Shape Similarity and Visual Parts.
Human perception of shape is based on visual parts of objects  to a point that a single, significant visual part is su#cient to recognize  the whole object. For example, if you see a hand in the door,  you expect a human behind the door. Therefore, a cognitively motivated  shape similarity measure for recognition applications should be based on  visual parts. This cognitive assumption leads to two related problems  of scale selection and subpart selection. To find a given query part Q  as part of an object C, Q needs to have a correct size with regards to  C (scale selection). Assuming that the correct size is selected, the part  Q must be compared to all possible subparts of C (subpart selection).
Tree%2Dstructured Partitioning Based on Splitting Histograms of Distances.

Topologies for the digital spaces Z2 and Z3.
We show that there are only two topologies in Z   and five topologies in Z   whose connected sets are connected in the intuitive sense. Both topologies for Z   are well known (e.g., one is presented in D. Marcus, F. Wyse et al., Amer. Math. Monthly 77, pp. 1119, 1979, and the second in E. Khalimsky et al., Topology and its Applications 36, pp. 1--17, 1990) and found applications in computer graphics and computer vision (e.g. A. Rosenfeld, Amer. Math. Monthly 77, pp. 621--630, 1979, and T. Y. Kong et al., Amer. Math. Monthly 98, pp. 901--917, 1991). Two of the five topologies for Z   are products of the topologies known from Z      . The remaining three topologies for Z   are also generated from the two topologies for Z   , however, they are not product topologies. Key Words Digital Topology, Alexandro# Topology, Digital Plane, Digital Space 1 
The choice of vantage objects for image retrieval.
Suppose that we have a matrix of dissimilarities between n images of a database. For a new image, we would like to select the most similar image of our database. Because it may be too expensive to compute the dissimilarities for the new object to all images of our database, we want to find p &lt;&lt; n &#034;vantage objects&#034; (Vleugels and Veltkamp, 2002) from our database in order to select a matching image according to the least Euclidean distance between the vector of dissimilarities between the new image and the vantage objects and the corresponding vector for the images of the database. In this paper we treat the choice of suitable vantage objects. We suggest a loss measure to assess the quality of a set of vantage objects: For every image, we select a matching image from the remaining images of the database by use of the vantage set, and we average the resulting dissimilarities. We compare two classes of choice strategies: The first one is based on a stepwise forward selection of vantage objects to optimize the loss measure. The second is to choose objects as representative as possible for the whole range of the database.
Automatic Recognition of Unpredictable Events in Videos.
The presented approach allows us to recognize frames in video sequence that are significantly different from the previous and/or following frames. In this way we are able to detect unpredictable events in videos. We map a video sequence to a polygonal trajectory by mapping each frame to a feature vector and joining the vectors representing consecutive frames by line segments. Shape analysis of the obtained polygonal curve allows us to detect frames representing unpredictable events. We demonstrate the performance of our approach on surveillance videos.
Recovering a Polygon from Noisy Data.

Special issue Shape Representation and Similarity for Image Databases.

Application of planar shape comparison to object retrieval in image databases.
A similarity measure for silhouettes of 2D objects is presented, and its properties  are analyzed with respect to retrieval of similar objects in image databases. To  reduce influence of digitization noise as well as segmentation errors the shapes are  simplified by a new process of digital curve evolution. To compute our similarity  measure, we first establish the best possible correspondence of visual parts (without  explicitly computing the visual parts). Then the similarity between corresponding  parts is computed and summed. Experimental results show that our shape matching  procedure gives an intuitive shape correspondence and is stable with respect to noise  distortions.
Shape Descriptors for Non%2DRigid Shapes with a Single Closed Contour.
The Core Experiment CE-Shape-1 for shape descriptors performed for the MPEG-7 standard gave a unique opportunity to compare various shape descriptors for non-rigid shapes with a single closed contour. There are two main differences with respect to other comparison results reported in the literature: (1) For each shape descriptor, the experiments were carried out by an institute that is in favor of this descriptor. This implies that the parameters for each system were optimally determined and the implementations were throughly tested. (2) It was possible to compare the performance of shape descriptors based on totally different mathematical approaches. A more theoretical comparison of these descriptors seems to be extremely hard. In this paper we report on the MPEG-7 Core Experiment CE-Shape1. 1.
Automatic Extraction of Relevant Frames from Videos by Polygon Simplification.

Schematizing Maps Simplification of Geographic Shape by Discrete Curve Evolution.
Shape simplification in map-like representations is used for two  reasons: either to abstract from irrelevant detail to reduce a map user&#039;s  cognitive load, or to simplify information when a map of a smaller scale is  derived from a detailed reference map. We present a method for abstracting  simplified cartographic representations from more accurate spatial data. First,  the employed method of discrete curve evolution developed for simplifying  perceptual shape characteristics is explained. Specific problems of applying the  method to cartographic data are elaborated. An algorithm is presented, which  on the one hand simplifies spatial data up to a degree of abstraction intended by  the user; and which on the other hand does not violate local spatial ordering  between (elements of) cartographic entities, since local arrangement of entities  is assumed to be an important spatial knowledge characteristic. The operation  of the implemented method is demonstrated using two different examples of  cartographic data.
Relevance Ranking of Video Data using Hidden Markov Model Distances and Polygon Simplification.
A video can be mapped into a multidimensional signal in a non-Euclidean space, in a way that translates the more predictable passages of the video into linear sections of the signal. These linear sections can be filtered out by techniques similar to those used for simplifying planar curves. Different degrees of simplification can be selected. We have refined such a technique so that it can make use of probabilistic distances between statistical image models of the video frames. These models are obtained by applying hidden Markov model techniques to random walks across the images. Using our techniques, a viewer can browse a video at the level of summarization that suits his patience level. Applications include the creation of a smart fast-forward function for digital VCRs, and the automatic creation of short summaries that can be used as previews before videos are downloaded from the Web.  Keywords: Browsing, skimming, summarization, video segmentation, HMM, random walk, Markov model, i...
Continuity of discrete curve evolution.

Polygon Evolution by Vertex Deletion.
Abstract. We propose a simple approach to evolution of polygonal curves that is specially designed to t discrete nature of curves in digital images. It leads to simpli cation of shape complexity withnoblurring (i.e., shape rounding) e ects and no dislocation of relevant features. Moreover, in our approach the problem to determine the size of discrete steps for numerical implementations does not occur, since our evolution method leads in a natural way to a nite number of discrete evolution steps which are just the iterations of a basic procedure of vertex deletion.
Shape Description and Search for Similar Objects in Image Databases.

Contour%2DBased Shape Similarity.
Abstract. This paper gives an overview of shape dissimilarity measure properties, such as metric and robustness properties, and of retrieval performance measures. Fifteen shape similarity measures are shortly described and compared. Their retrieval results on the MPEG-7 Core Experiment CE-Shape-1 test set as reported in the literature and obtained by a reimplementation are compared and discussed. 1
Convexity Rule for Shape Decomposition Based on Discrete Contour Evolution.
We concentrate here on decomposition of 2D objects into meaningful parts of visual form,orvisual parts. It is a simple observation that convex parts of objects determine visual parts. However, the problem is that many significant visual parts are not convex, since a visual part may have concavities. We solve this problem by identifying convex parts at different stages of a proposed contour evolution method in which significant visual parts will become convex object parts at higher stages of the evolution. We obtain a novel rule for decomposition of 2D objects into visual parts, called the hierarchical convexity rule, which states that visual parts are enclosed by maximal convex (with respect to the object) boundary arcs at different stages of the contour evolution. This rule determines not only parts of boundary curves but directly the visual parts of objects. Moreover, the stages of the evolution hierarchy induce a hierarchical structure of the visual parts. The more advanced the stage of contour evolution, the more significant is the shape contribution of the obtained visual parts. c ○ 1999 Academic Press Key Words: visual parts; discrete curve evolution; digital curves; digital straight line segments; total curvature; shape hierarchy; digital geometry. 1.
Digitizations preserving shape.
We present several methods for simulation of Japanese lacquer ware, a prominent Far East Asian handicraft  art. We consider two most popular kinds of Japanese lacquer ware made by the makie and nashiji techniques.
Digital geometric methods in document image analysis.

Digital Geometric Methods in Image Analysis and Compression.
Abstract. One of the important problems related to image analysis and compression is finding repeated structure. Although the focus of this paper is developing digital geometric models and methods for finding regular structure in digital document images, the applicability of the digital geometric approach is also demonstrated on images taken under orthographic and perspective projection. First, a fast linear-time algorithm is given to compute the static threshold that minimizes the non-welt-composedness or weak connectivity of the document image. Next, a new digital similarity measure is introduced that outperforms the standard similarity measures, including the Hansdorff distance, with respect to determining if two discrete objects in the image are digitizations of the same prototype. This measure is then used in a model-based compression algorithm, and a variation of the algorithm is developed for finding structure in images taken under affine and perspective transformations. 1
Shape Decomposition and Shape Similarity Measure.

Discrete Approach to Curve Evolution.

Preserving Topology by a Digitization Process.

Supportedness and tameness differentialless geometry of plane curves.
We introduce a class of planar arcs and curves, called tame arcs, which is general enough to describe (parts of) the boundaries of planar real objects. A tame arc can have a smooth parts as well as sharp (non-differentiable) corners. Thus, a polygonal arc is tame. On the other hand, this class of arcs is restrictive enough to rule out pathological arcs which have infinitely many inflections or which turn infinitely often: A tame arc can have only finitely many inflections, and its total absolute turn must be finite.
3D Well%2DComposed Pictures.
By a segmented image, we mean a digital image in which each point is assigned a unique label that indicates the object to which it belongs. By the foreground (objects) of a segmented image, we mean the objects whose properties we want to analyze, and by the background all the other objects of a digital image. If one adjacency relation is used for the foreground of a 3D segmented image (e.g., 6-adjacency) and a di#erent one for the background (e.g., 26-adjacency), then interchanging the foreground and the background can change the connected components of the digital picture. Hence, the choice of foreground and of background is critical for the results of the subsequent analysis (like object grouping), especially in cases where it is not clear at the beginning of the analysis what constitutes the foreground and what the background, since this choice immediately determines the connected components of the digital picture. A special
A Realistic Digitization Model of Straight Lines.
Understanding digital lines comprises two components: i) determining whether a given digital set is a digital line segment, i.e. whether there exists a real straight line in IR  2  that digitizes to it, and ii) recovering the space of straight lines which digitize to a given digital line segment. Although these problems have been extensively studied by researchers in computer vision and digital geometry, the primary digitization model that has been used is object boundary quantization which is not a realistic sensor model in computer vision.In this paper, we present a realistic mathematical model of a digitized edge which handles both blurring and arbitrary thresholding. We show that a thresholded digital image of a blurred half-plane obtained for some unknown threshold value is equal to the image of a perfectly focused half-plane with the same slope obtained by object boundary quantization. This result implies that recovering the slope of a blurred half-plane, given its image obtained...
An Algorithm for a 3D Simplicity Test.

Conditions that Guarantee a Digitization Process Preserves Topology.

Well%2DComposed Sets.
A special class of subsets of binary digital images called &amp;quot;well-composed sets &amp;quot; is defined. The sets of this class have very nice topological properties; for example, the Jordan Curve Theorem holds for them, their Euler characteristic is locally computable, and they have only one connectedness relation, since 4- and 8-connectedness are equivalent. This implies that many basic algorithms used in computer vision become simpler. There are real advantages in applying thinning algorithms to well-composed sets. For example, thinning is an internal operation on these sets and the problems with irreducible &amp;quot;thick &amp;quot; sets disappear. Furthermore, we prove that the skeletons obtained are &amp;quot;one point thick &amp;quot; and we give a formal definition of this concept. We also show that these skeletons have a graph structure and we define what this means.
Digitizations Preserving Topological and Differential Geometric Properties.
In this paper we present conditions which guarantee that every digitization process preserves important topological and differential geometric properties. These conditions also allow us to determine the correct digitization resolution for a given class of real objects. Knowing that these properties are invariant under digitization, we can then use them in feature-based recognition. Moreover, these conditions imply that only a few digital patterns can occur as neighborhoods of boundary points in the digitization. This is very useful for noise detection, since if the neighborhood of a boundary point does not match one of these patterns, it must be due to noise. Our definition of a digitization approximates many real digitization processes. The digitization process is modeled as a mapping from continuous sets representing real objects to discrete sets represented as digital images. We show that an object A and the digitization of  A are homotopy equivalent. This, for example, implies that...
Generalized convexity CP3 and boundaries of convex sets.
definition can be generalized in various ways. One class of generalizations makes use of k-tuples, rather than pairs, of points--for example, Valentine&#039;s property P3: For every triple of points P, Q, R of S, at least one of the line segments PQ, QR, or RP is contained in S. It can be shown that if a set has property P3, it is a union of at most three convex sets. In this paper we study a property closely related to, but weaker than, P3 &#039; We say that S has property CP3 (&amp;quot;collinear P3&amp;quot;) if P3 holds for all collinear triples of points of S. We prove that a closed curve is the boundary of a convex set, and a simple arc is part of the boundary of a convex set, iff they have property CP a. This result appears to be the first simple characterization of the boundaries of convex sets; it solves a problem studied over 30 years ago by Menger and Valentine. Convexity Convex arcs Convex curves Generalized convexity Boundaries A set S is convex if for every pair of points P, QeS, the line segment PQ is contained in S. This definition can be generalized in various ways. For example, (1) S is called starshapedfrom Po E S if PoQ is contained in S
Semi%2Dproximity continuous functions in digital images.
Starting with the intuitive concept or nearness &#034; as a binar,, relation, semi-proximity spaces (sp-spaces) are defined. The restrictions on semi-proximity spaces are weaker than on topological proximity spaces. Thus, semi-proximity spaces generalize classical topological spaces. Moreover, it is possible to describe all digital pictures used in computer vision and computer graphics as non-trivial semi-proximity spaces, which is not possible in classical topology. Therefore, we use semi-proximity spaces to establish a formal relationship between the &#034;topological &#034; concepts of digital image processing and their continuous counterparts in [~&#034; Especially interesting are continuous functions in semi-proximity spaces which are called &#034;semi-proximity &#034; continuous functions. They can be used for characterizing well-behaved operations on digital images such as thinning. It will be shown that the deletion of a simple point can be treated as a semi-proximity continuous function. These properties and the fact that a variety of nearness relations can be defined on digital pictures indicate that semi-proximity continuous functions are a useful tool in the difficult task of shape description.
Multicolor well%2Dcomposed pictures.

Toward Non%2DParametric Digital Shape Representation and Recovery.

Invariant Thinning and Distance Transform.

Orientation and Qualitative Angle for Spatial Reasoning.

R%E4umliches Schlie%DFen und Berechenbarkeit.

Digitale und Allgemeine Topologie in der bildhaften Wissensrepr%E4sentation.

Connection Relations and Quantifier Scope.
A formalism will be presented in this paper which makes it possible to realise the idea of assigning only one scope-ambiguous representation to a sentence that is ambiguous with regard to quantifier scope. The scope determination results in extending this representation with additional context and world knowledge conditions. If there is no scope determining information, the formalism can work further with this scope-ambiguous representation. Thus scope information does not have to be completely determined. Many natural language sentences have
On Hybrid Reasoning for Processing Spatial Expressions.

An Indexing Technique For Implementing Command Relations.

Topologie in Depiktionen.

